#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 22;
const int L = 1048578;
const int mod = 1e9+9;

int n,len,a[N][L],b[N][L],c[N][L],A[L],B[L];

void FMT(int *f,int l){
	for(int i = 0;i <= l;i++)
		for(int j = 0;j < 1<<l;j++)
			if(j >> i & 1)
				(f[j] += f[j^1<<i]) %= mod;
}

void IFMT(int *f,int l){
	for(int i = 0;i <= l;i++)
		for(int j = 0;j < 1<<l;j++)
			if(j >> i & 1)
				(f[j] += mod - f[j^1<<i]) %= mod;
}

int popcnt(int x){int res=0;for(;x;x>>=1)res+=x&1;return res;}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in;len = 1 << n;
	for(int i = 0;i < len;i++) A[i] = in,a[popcnt(i)][i] += A[i];
	for(int i = 0;i < len;i++) B[i] = in,b[popcnt(i)][i] += B[i];
	for(int i = 0;i <= n;i++) FMT(a[i],n),FMT(b[i],n);
	for(int i = 0;i <= n;i++){
		for(int j = 0;j <= i;j++)
			for(int k = 0;k < 1 << n;k++)
				(c[i][k] += (ll) a[j][k] * b[i-j][k] % mod) %= mod;
		IFMT(c[i],n);
	}
	for(int i = 0;i < len;i++) printf("%d%c",c[popcnt(i)][i]," \n"[i==len-1]);
	return 0;
}
